export type DataNode = {
  title: string;
  key: string;
  children?: DataNode[];
};

function findNodeByKey(data: DataNode[], key: string): DataNode | undefined {
  for (const node of data) {
    if (node.key === key) {
      return node;
    }
    if (node.children) {
      const foundNode = findNodeByKey(node.children, key);
      if (foundNode) {
        return foundNode;
      }
    }
  }
  return undefined;
}

function collectChildKeys(
  node: DataNode | undefined,
  result: string[] = [],
): string[] {
  if (!node || !node.children) {
    return result;
  }
  for (const child of node.children) {
    result.push(child.key);
    collectChildKeys(child, result);
  }
  return result;
}

// 在treeData中找到对应key值下所有子集的keys
export function getChildKeys(key: string, data: DataNode[]): string[] {
  const targetNode = findNodeByKey(data, key);
  return collectChildKeys(targetNode);
}

// 找到当前节点所有的父节点
export const getParentKeys = (
  targetKey: string,
  treeData: DataNode[],
): string[] => {
  const findPath = (node: DataNode, currentPath: string[]): string[] | null => {
    if (node.key === targetKey) {
      return currentPath;
    }
    if (node.children) {
      for (const child of node.children) {
        const result = findPath(child, [...currentPath, node.key]);
        if (result) {
          return result;
        }
      }
    }
    return null;
  };

  for (const rootNode of treeData) {
    const path = findPath(rootNode, []);
    if (path) {
      return path;
    }
  }

  return [];
};

const gatherKeys = (tree: DataNode[]): string[] => {
  const keys: string[] = [];
  function recursiveCollect(nodes: DataNode[]) {
    for (const node of nodes) {
      keys.push(node.key);
      if (node.children) {
        recursiveCollect(node.children);
      }
    }
  }
  recursiveCollect(tree);
  return keys;
};

// 找到传入keys的每一项的所有的子节点，并返回result对象，对象的key为keys中每一项的key，value为其所有子节点
export const getAllChildKeys = (treeData: DataNode[]) => {
  const keys = gatherKeys(treeData);
  const result: Record<string, string[]> = {};
  keys.forEach((i) => {
    result[i] = getChildKeys(i, treeData);
  });
  return result;
};

// 返回子集都被选中的父级的key
export const getFullChildrenSelectedKey = (
  treeData: DataNode[],
  keys: string[],
): string[] => {
  // 获取到treeData中每一项的所有子集，并组成对象
  const keyAndAllChildrenObj = getAllChildKeys(treeData);
  const entriesArr = Object.entries(keyAndAllChildrenObj);
  const result: string[] = [];
  entriesArr.forEach(([key, value]) => {
    if (value?.length && value.every((i) => keys.includes(i))) {
      result.push(key);
    }
  });
  return result;
};
